Completely Fair Scheduler

Completely Fair Scheduler (CFS) は、Linuxカーネル 2.6.23 にマージされたタスクスケジューラである。プロセス実行に必要なCPUリソース割り当てを行い、全体としてCPU利用効率を最大化しつつ対話的性能も最大化する。

コン・コリバス（英語版）のCPUスケジューリングに関する業績、特に Rotating Staircase Deadline と名付けたフェア・シェア・スケジューリング（英語版）の実装に強く影響され、インゴ・モルナー（英語版）が従来のO(1)スケジューラ（英語版）の代替としてCFSを開発した^[1]。

それまでの Linux 2.6 カーネルで使われていたO(1)スケジューラ（英語版）とは対照的に、CFSスケジューラの実装はランキュー（英語版）を採用していない。代わりに赤黒木で将来のタスク実行の予定表を実装している。さらにこのスケジューラはナノ秒単位の実行時間計測を行い、ナノ秒単位で個々のプロセスにCPUを割り当てる（したがって、それまでのタイムスライスの観念より細かい）。このように正確な知識を使うことで例えば、プロセスが対話的か否かを判定するのに特別なヒューリスティクスを使う必要がなくなる^[2]。

従来のO(1)スケジューラと同様、CFSは "sleeper fairness" という概念を採用している。これは、スリープまたはウェイトしているタスクとランキュー上で待っているタスクを公平に扱うという方針である。したがって時間の大部分をユーザーの入力などのイベントを待つことに費やしている対話型タスクであっても、必要ならそれなりのCPU時間を得ることができる。

1. ^ Molnár, Ingo (13 April 2007). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
2. ^ Andrews, Jeremy (2007年4月18日). “Linux: The Completely Fair Scheduler”. KernelTrap. 2012年6月29日時点のオリジナルよりアーカイブ。2012年9月12日閲覧。^{[リンク切れ]}